import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        ProcessTest pt = new ProcessTest();
        pt.menu();
    }
}

class ProcessTest {
    static class Program {
        String name;
        int running_time;
        int enter_time;
        int priority;
        int done_time;    //用于时间片轮转
        int copyRunning_time;  //用于时间片轮转
        int start_time;
        Program next;
    }

    static class ProgramQueue {
        Program firstProg;
        Program LastProg;
        int size;
    }


    void Queueinit(ProgramQueue queue) {
        if (queue == null) return;
        queue.size = 0;
        queue.LastProg = new Program();
        queue.firstProg = queue.LastProg;
    }

    void print(Program[] pro, int num) {
        for (int i = 0; i < num; i++) {
            System.out.printf("%d ", pro[i].enter_time);
        }
    }

    void printQueue(ProgramQueue queue) {
        Program p = queue.firstProg.next;
        while (p != null) {
            System.out.printf("%s ", p.name);
            p = p.next;
        }
        System.out.print("\n");
    }


    void EnterQueue(ProgramQueue queue, Program pro) {   //加入进程队列
        queue.LastProg.next = new Program();
        queue.LastProg = queue.LastProg.next;
        queue.LastProg.enter_time = pro.enter_time;
        queue.LastProg.name = pro.name;
        // memcpy(queue.LastProg.name, pro.name, sizeof(pro.name));
        queue.LastProg.priority = pro.priority;
        queue.LastProg.running_time = pro.running_time;
        queue.LastProg.copyRunning_time = pro.copyRunning_time;
        queue.LastProg.start_time = pro.start_time;
        queue.size++;
    }

    Program poll(ProgramQueue queue) {
        Program temp = queue.firstProg.next;
        if (temp == queue.LastProg) {
            queue.LastProg = queue.firstProg;
            queue.size--;
            return temp;
        }
        queue.firstProg.next = queue.firstProg.next.next;
        queue.size--;
        return temp;
    }

    void inputProgram(Program[] pro, int num) {
        Scanner scanner = new Scanner(System.in);
        for (int i = 0; i < num; i++) {
            Program prog = new Program();
            System.out.printf("请输入第%d个进程的名字，到达时间，服务时间，优先级\n", i + 1);
            prog.name = scanner.next();
            prog.enter_time = scanner.nextInt();
            prog.running_time = scanner.nextInt();
            prog.copyRunning_time = prog.running_time;
            prog.priority = scanner.nextInt();
            pro[i] = prog;
        }
    }

    void sortWithEnterTime(Program[] pro, int num) {
        for (int i = 1; i < num; i++) {
            for (int j = 0; j < num - i; j++) {
                if (pro[j].enter_time > pro[j + 1].enter_time) {
                    Program temp = pro[j];
                    pro[j] = pro[j + 1];
                    pro[j + 1] = temp;
                }
            }
        }
    }

    void FCFS(Program[] pro, int num) {
        System.out.print("进程 到达时间  服务时间 开始时间 完成时间 周转时间 带权周转时间\n");
        sortWithEnterTime(pro, num);    //按照进入顺序排序
        ProgramQueue queue = new ProgramQueue();
        Queueinit(queue);
        EnterQueue(queue, pro[0]);
        int time = pro[0].enter_time;
        int pronum = 1;    //记录当前的进程
        float sum_T_time = 0, sum_QT_time = 0;
        while (queue.size > 0) {
            Program curpro = poll(queue);   //从进程队列中取出进程
            if (time < curpro.enter_time)
                time = curpro.enter_time;
            int done_time = time + curpro.running_time;
            int T_time = done_time - curpro.enter_time;
            sum_T_time += T_time;
            float QT_time = (float) (T_time / (curpro.running_time + 0.0));
            sum_QT_time += QT_time;
            for (int tt = time; tt <= done_time && pronum < num; tt++) {    //模拟进程的执行过程

                if (tt >= pro[pronum].enter_time) {
                    EnterQueue(queue, pro[pronum]);
                    pronum++;
                }
            }
            System.out.printf("%s\t%d\t%d\t%d\t%d\t%d\t%.2f\n", curpro.name, curpro.enter_time, curpro.running_time, time, done_time
                    , T_time, QT_time);
            time += curpro.running_time;
            if (queue.size == 0 && pronum < num) {   //防止出现前一个进程执行完到下一个进程到达之间无进程进入
                EnterQueue(queue, pro[pronum]);
                pronum++;
            }
        }
        System.out.printf("平均周转时间为%.2f\t平均带权周转时间为%.2f\n", sum_T_time / (num + 0.0), sum_QT_time / (num + 0.0));
    }

    void sortWithLongth(Program[] pro, int start, int end) {
        int len = end - start;
        if (len == 1) return;
        for (int i = 1; i < len; i++) {
            for (int j = start; j < end - i; j++) {
                if (pro[j].running_time > pro[j + 1].running_time) {
                    Program temp = pro[j];
                    pro[j] = pro[j + 1];
                    pro[j + 1] = temp;
                }
            }
        }
    }

    void SJF(Program[] pro, int num) {
        System.out.print("进程 到达时间  服务时间 开始时间 完成时间 周转时间 带权周转时间\n");
        sortWithEnterTime(pro, num);
        ProgramQueue queue = new ProgramQueue();
        Queueinit(queue);
        EnterQueue(queue, pro[0]);
        int time = pro[0].enter_time;
        int pronum = 1;    //记录当前的进程
        float sum_T_time = 0, sum_QT_time = 0;
        while (queue.size > 0) {
            Program curpro = poll(queue);   //从进程队列中取出进程
            if (time < curpro.enter_time)
                time = curpro.enter_time;
            int done_time = time + curpro.running_time;
            int T_time = done_time - curpro.enter_time;
            float QT_time = (float) (T_time / (curpro.running_time + 0.0));
            sum_T_time += T_time;
            sum_QT_time += QT_time;
            int pre = pronum;
            for (int tt = time; tt <= done_time && pronum < num; tt++) {    //模拟进程的执行过程
                if (tt >= pro[pronum].enter_time) { // 统计从此任务开始到结束之间有几个进程到达
                    pronum++;
                }
            }
            sortWithLongth(pro, pre, pronum);//将到达的进程按照服务时间排序
            for (int i = pre; i < pronum; i++) {    //将进程链入队列
                EnterQueue(queue, pro[i]);
            }
            pre = pronum;
            System.out.printf("%s\t%d\t%d\t%d\t%d\t%d\t%.2f\n", curpro.name, curpro.enter_time, curpro.running_time, time, done_time
                    , T_time, QT_time);
            time += curpro.running_time;
            if (queue.size == 0 && pronum < num) {   //防止出现前一个进程执行完到下一个进程到达之间无进程进入
                EnterQueue(queue, pro[pronum]);
                pronum++;
            }
        }
        System.out.printf("平均周转时间为%.2f\t平均带权周转时间为%.2f\n", sum_T_time / (num + 0.0), sum_QT_time / num);
    }

    void sortWithPriority(Program[] pro, int start, int end) {
        int len = end - start;
        if (len == 1) return;
        for (int i = 1; i < len; i++) {
            for (int j = start; j < end - i; j++) {
                if (pro[j].priority > pro[j + 1].priority) {
                    Program temp = pro[j];
                    pro[j] = pro[j + 1];
                    pro[j + 1] = temp;
                }
            }
        }
    }

    void HPF(Program[] pro, int num) {
        System.out.print("进程 到达时间  服务时间 开始时间 完成时间 周转时间 带权周转时间\n");
        sortWithEnterTime(pro, num);
        ProgramQueue queue = new ProgramQueue();
        Queueinit(queue);
        EnterQueue(queue, pro[0]);
        int time = pro[0].enter_time;
        int pronum = 1;    //记录当前的进程
        float sum_T_time = 0, sum_QT_time = 0;
        while (queue.size > 0) {
            Program curpro = poll(queue);   //从进程队列中取出进程
            if (time < curpro.enter_time)
                time = curpro.enter_time;
            int done_time = time + curpro.running_time;
            int T_time = done_time - curpro.enter_time;
            float QT_time = (float) (T_time / (curpro.running_time + 0.0));
            sum_T_time += T_time;
            sum_QT_time += QT_time;
            int pre = pronum;
            for (int tt = time; tt <= done_time && pronum < num; tt++) {    //模拟进程的执行过程
                if (tt >= pro[pronum].enter_time) { // 统计从此任务开始到结束之间有几个进程到达
                    pronum++;
                }
            }
            sortWithPriority(pro, pre, pronum);//将到达的进程按照服务时间排序
            for (int i = pre; i < pronum; i++) {    //将进程链入队列
                EnterQueue(queue, pro[i]);
            }
            pre = pronum;
            System.out.printf("%s\t%d\t%d\t%d\t%d\t%d\t%.2f\n", curpro.name, curpro.enter_time, curpro.running_time, time, done_time
                    , T_time, QT_time);
            time += curpro.running_time;
            if (queue.size == 0 && pronum < num) {   //防止出现前一个进程执行完到下一个进程到达之间无进程进入
                EnterQueue(queue, pro[pronum]);
                pronum++;
            }
        }
        System.out.printf("平均周转时间为%.2f\t平均带权周转时间为%.2f\n", sum_T_time / (num + 0.0), sum_QT_time / (num + 0.0));
    }

    void RR(Program[] pro, int num) {
        System.out.print("请输入时间片大小");
        int timeslice;
        Scanner scanner = new Scanner(System.in);
        timeslice = scanner.nextInt();
        System.out.print("进程 到达时间  服务时间 进入时间 完成时间 周转时间 带权周转时间\n");
        sortWithEnterTime(pro, num);
        ProgramQueue queue = new ProgramQueue();
        Queueinit(queue);
        pro[0].start_time = pro[0].enter_time;
        EnterQueue(queue, pro[0]);
        int time = 0;
        int pronum = 1;
        float sum_T_time = 0, sum_QT_time = 0;
        while (queue.size > 0) {
            Program curpro = poll(queue);    // 从队列中取出头节点
            if (time < curpro.enter_time)
                time = curpro.enter_time;
            if (timeslice >= curpro.running_time) {   // 如果剩余时间小于时间片  则此任务完成
                for (int tt = time; tt <= time + curpro.running_time && pronum < num; tt++) {    // 模拟进程的执行过程
                    if (tt >= pro[pronum].enter_time) { // 统计从此任务开始到结束之间有几个进程到达
                        pro[pronum].start_time = tt;
                        EnterQueue(queue, pro[pronum]);
                        pronum++;
                    }
                }
                time += curpro.running_time;
                curpro.running_time = 0;
                curpro.done_time = time;
                int T_time = curpro.done_time - curpro.start_time;
                float QT_time = (float) (T_time / (curpro.copyRunning_time + 0.0));
                sum_T_time += T_time;
                sum_QT_time += QT_time;
                System.out.printf("%s\t%d\t%d\t  %d\t   %d\t %d\t  %.2f\n", curpro.name, curpro.enter_time, curpro.copyRunning_time,
                        curpro.start_time, curpro.done_time, T_time, QT_time);
                if (queue.size == 0 && pronum < num) {   //防止出现前一个进程执行完到下一个进程到达之间无进程进入
                    pro[pronum].start_time = pro[pronum].enter_time;
                    EnterQueue(queue, pro[pronum]);
                    pronum++;
                }
                continue;
            }
            for (int tt = time; tt <= time + timeslice && pronum < num; tt++) {    //模拟进程的执行过程
                if (tt >= pro[pronum].enter_time) { // 统计从此任务开始到结束之间有几个进程到达
                    pro[pronum].start_time = tt;
                    EnterQueue(queue, pro[pronum]);
                    pronum++;
                }
            }
            time += timeslice;
            curpro.running_time -= timeslice;
            EnterQueue(queue, curpro);    //当前程序未完成  继续添加到队列中
            if (queue.size == 0 && pronum < num) {   //防止出现前一个进程执行完到下一个进程到达之间无进程进入
                pro[pronum].start_time = pro[pronum].enter_time;
                EnterQueue(queue, pro[pronum]);
                pronum++;
            }
        }
        System.out.printf("平均周转时间为%.2f\t平均带权周转时间为%.2f\n\n", sum_T_time / (num + 0.0), sum_QT_time / (num + 0.0));
    }

    void choiceMenu() {
        System.out.println("请选择进程调度算法：\n");
        System.out.println("1.先来先服务算法\n2.短进程优先算法\n3.高优先级优先\n4.时间片轮转算法\n");
    }

    void menu() {
        int proNum;
        Scanner scanner = new Scanner(System.in);
        System.out.print("请输入进程的个数：");
        proNum = scanner.nextInt();
        Program[] pro = new Program[proNum];
        inputProgram(pro, proNum);
        choiceMenu();
        int choice;
        while (true) {
            choice = scanner.nextInt();
            switch (choice) {
                case 1:
                    FCFS(pro, proNum);
                    choiceMenu();
                    break;
                case 2:
                    SJF(pro, proNum);
                    choiceMenu();
                    break;
                case 3:
                    HPF(pro, proNum);
                    choiceMenu();
                    break;
                case 4:
                    RR(pro, proNum);
                    choiceMenu();
                    break;
                case 5:
                    return;
            }
        }
    }
}


